package double_pointer;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86185
 * Date: 2023-12-03
 * Time: 14:39
 */
public class Partition {
    public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode small = new ListNode(0, head);
        ListNode large = new ListNode(0, head);
        ListNode largeHead = large;
        ListNode smallHead = small;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(2);
        ListNode listNode1 = new ListNode(1);
//        ListNode listNode2 = new ListNode(3);
//        ListNode listNode3 = new ListNode(2);
//        ListNode listNode4 = new ListNode(5);
//        ListNode listNode5 = new ListNode(2);
        listNode.next = listNode1;
//        listNode1.next = listNode2;
//        listNode2.next = listNode3;
//        listNode3.next = listNode4;
//        listNode4.next = listNode5;
        listNode1.next = null;
        partition(listNode, 2);
    }
}
